package qjc.b_双指针;

public class d_接雨水 {
    /**
     * 初始化接雨水的总量，初始化两个数组，分别存储每个位置左边和右边的最大高度，
     * 计算每个位置左边的最大高度，计算每个位置右边的最大高度，遍历每个位置，
     * 计算该位置可以接的雨水量，当前位置可以接的雨水量取决于左右两边最大高度的较小值，
     * 如果当前位置的柱子高度小于左右两边的最大高度的较小值，
     * 当前位置可以接的雨水量为 min - height[i]
     */
    public int trap(int[] height) {
        int sum = 0;
        int[] left = new int[height.length];
        int[] right = new int[height.length];
        for (int i = 1; i < left.length; i++) {
            left[i] = Math.max(left[i - 1],height[i - 1]);
        }
        for (int i = height.length - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1],height[i + 1]);
        }
        for (int i = 0; i < height.length; i++) {
            int min = Math.min(left[i], right[i]);
            if (min > height[i]) {
                sum += min - height[i];
            }
        }
        return sum;
    }
}
